/*
     RoadRunner - an automatic wrapper generation system for Web data sources
     Copyright (C) 2003  Valter Crescenzi - crescenz@dia.uniroma3.it

     This program is  free software;  you can  redistribute it and/or
     modify it  under the terms  of the GNU General Public License as
     published by  the Free Software Foundation;  either version 2 of
     the License, or (at your option) any later version.

     This program is distributed in the hope that it  will be useful,
     but  WITHOUT ANY WARRANTY;  without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with this program; if not, write to the:

     Free Software Foundation, Inc.,
     59 Temple Place, Suite 330,
     Boston, MA 02111-1307 USA

     ----

     RoadRunner - un sistema per la generazione automatica di wrapper su sorgenti Web
     Copyright (C) 2003  Valter Crescenzi - crescenz@dia.uniroma3.it

     Questo  programma software libero;  lecito redistribuirlo  o
     modificarlo second  o i termini della Licenza Pubblica Generica GNU
     come � pubblicata dalla Free Software Foundation; o la versione 2
     della licenza o (a propria scelta) una versione successiva.

     Questo programma   distribuito nella speranza che sia  utile, ma
     SENZA  ALCUNA GARANZIA;  senza neppure la  garanzia implicita  di
     NEGOZIABILIT�  o di  APPLICABILIT� PER  UN PARTICOLARE  SCOPO. Si
     veda la Licenza Pubblica Generica GNU per avere maggiori dettagli.

     Questo  programma deve  essere  distribuito assieme  ad una copia
     della Licenza Pubblica Generica GNU; in caso contrario, se ne pu
     ottenere  una scrivendo  alla:

     Free  Software Foundation, Inc.,
     59 Temple Place, Suite 330,
     Boston, MA 02111-1307 USA

*/
/*
 * Backtracker.java
 * A backtracker based on ExpressionIterator
 * Created on December 29, 2003, 3:23 PM
 * @author  Valter Crescenzi
 */

package com.wolf_datamining.autoextracting.roadrunner.engine;

import java.util.*;

import com.wolf_datamining.autoextracting.roadrunner.ast.Expression;


public abstract class Backtracker extends ExpressionIterator {
    
    private Stack stack;
    private boolean enabled;
    private ExpressionIterator current;
    
    /** Creates a new instance of Backtracker */
    protected Backtracker(Expression initial) {
        this(iteratorOverSingleExp(initial));
    }
    
    protected Backtracker(ExpressionIterator initial) {
        this.stack = new Stack();
        this.stack.push(initial);
        this.enabled = true;
        this.current = null;
    }
    
    public boolean backtrackingEnabled() {
        return enabled;
    }
    public void setBacktracking(boolean enabled) {
        this.enabled = enabled;
    }
    
    protected abstract ExpressionIterator successor(Expression exp);
    protected abstract boolean goalTest(Expression exp);
    
    protected void start() {}
    protected void back() {}
    protected Expression gotFinal(Expression exp) { return exp;}
    protected void expired() {}
    
    protected Expression computeNext() {
        start();
        while (!stack.isEmpty()) {
            this.current = (ExpressionIterator)stack.peek();
            try {
                if (!current.hasNext()) {
                    if (!backtrackingEnabled()) break;
                    stack.pop();
                    back();
                    continue;
                }
                
                Expression result = current.next();
                if (goalTest(result)) {
                    return gotFinal(result);
                }
                else {
                    ExpressionIterator next = successor(result);
                    this.stack.push(next);
                }
            }
            catch (FailException f) {
                // fail() has been called: ignore current "result"
            }
        }
        expired();
        return null;
    }
    
    protected ExpressionIterator getCurrent() {
        return this.current;
    }
    
    protected void fail() {
        throw new FailException();
    }
    
    protected class FailException extends RuntimeException {
        protected FailException() {
        }
    }
    
}
